package com.hj.sort;

import java.util.Arrays;

/**
 * @author hj
 * @Date 2022/1/5
 * @Description: 归并排序
 */
public class MergeSort {

    public void mergeSort(int[] array) {
        if (null == array) {
            return;
        }
        int[] aux = new int[array.length];
        sort(array, 0, array.length - 1, aux);
    }

    private void sort(int[] array, int left, int right, int[] aux) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 先分后合
            sort(array, left, mid, aux);
            sort(array, mid + 1, right, aux);
            merge(array, left, mid, right, aux);
        }
    }

    private void merge(int[] array, int left, int mid, int right, int[] aux) {
        int t = 0;
        int l = left;
        int m = mid + 1;
        // 判断元素值大小，按大小排序到辅助数组上
        while (l <= mid && m <= right) {
            if (array[l] <= array[m]) {
                aux[t++] = array[l++];
            } else {
                aux[t++] = array[m++];
            }
        }
        // 把剩余元素填充到辅助数组上
        while (l <= mid) {
            aux[t++] = array[l++];
        }
        while (m <= right) {
            aux[t++] = array[m++];
        }
        // 将辅助线数组上的元素复制到需要排序的数组上
        t = 0;
        while (left <= right) {
            array[left++] = aux[t++];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = {5, 9, 125, 6, 85, 97, 45, 3, 25, 64, 36, 98, 103, 45, 12, 35};
        mergeSort.mergeSort(array);
        System.out.println(Arrays.toString(array));
    }


}
